#include <iostream>
#include <vector>

using namespace std;
class Solution
{
public:
    bool isSubsequence(string s, string t)
    {
        int sLen = s.length(), tLen = t.length();
        int j = 0;
        // For index of s (or subsequence

        // Traverse s and t, and
        // compare current character
        // of s with first unmatched char
        // of t, if matched
        // then move ahead in s
        for (int i = 0; i < tLen and j < sLen; i++)
        {
            if (s[j] == t[i])
            {
                j++;
            }
        }

        // If all characters of s were found in t
        return j == sLen;
    }

    bool isSubsequence_2(string s, string t)
    {
        int idx = 0;
        for (int i = 0; i < t.size(); i++)
        {
            if (t[i] == s[idx])
            {
                idx++;
            }
        }
        return idx == s.size();
    }

    bool isSubsequence_3(string s, string t)
    {
        int m = s.length();
        int n = t.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        for (int i = 1; i <= m; i++)
        {
            dp[i][0] = 0;
        }
        for (int j = 0; j <= n; j++)
        {
            dp[0][j] = 1;
        }
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                dp[i][j] = (s[i - 1] == t[j - 1]) ? dp[i - 1][j - 1] : dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
};
int main()
{
    Solution solution;
    string s = "abc", t = "ahbgdc";
    cout << solution.isSubsequence_3(s, t) << endl;
    return 0;
}
